#include <vector>

using namespace std;

/* 快速排序 */
void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right)
        return;
    int pivot = partition(nums, left, right);
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

/* 哨兵划分 */
int partition(vector<int>& nums, int left, int right) {
    int i = left, j = right;
    int base = nums[left];
    while (i < j) {
        while (i < j && nums[j] >= base)
            j--;
        while (i < j && nums[i] <= base)
            i++;
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[left]);
    return i;
}
